package com.str.set;
public class LinkedSet implements Set, Cloneable {

// Inner class
  private static class SLLNode {
    Comparable data;
    SLLNode next;

    SLLNode() {}
    SLLNode(Comparable obj) { data = obj; }
    SLLNode(Comparable obj, SLLNode link) {  
      data = obj;
      next = link; 
    }

    public String toString()
    { return data.toString(); }
  }

  // Each LinkedSet value is an unbounded set whose elements are
  // comparable objects.

  // This set is represented as follows: first is a link to the
  // first node of a SLL containing the elements; card is the
  // number of elements.
  private SLLNode first;
  private int count;

// Constructor
  public LinkedSet() {
  // Construct a set, initially empty
    clear();
  }
    
// Modifiers  
  public final void clear() {  
    first = null;
    count = 0;
  }

  public void add(Object val) {
  // Inserts val into this set.
    Comparable item = (Comparable) val;
    SLLNode prior = null, curr = first;
    while (curr != null) {
      int comp = item.compareTo(curr.data);
      if (comp == 0) return;
      else if (comp < 0) break;
      prior = curr;
	  curr = curr.next;
	}
    SLLNode temp = new SLLNode(item, curr);
    if (prior == null)
      first = temp;
    else
      prior.next = temp;        
    count++;
  }

  public Object remove(Object val) {
    if (val instanceof Comparable) {
      Comparable item = (Comparable) val;
      // Deletes all occurrences of oldElement (if present) from this set.
      SLLNode prior = null, curr = first;
      while (curr != null) {
        int comp = item.compareTo(curr.data);
        if (comp == 0) {
          SLLNode temp = curr; 
          if (prior == null)
            first = curr.next;
          else 
            prior.next = curr.next;             
          count--;
          return temp;
        } 
        else if (comp < 0) break;
        prior = curr;
        curr = curr.next;
      }
    }
    return null;
  }

  public void union(Set that) {
    LinkedSet other = (LinkedSet) that;
    // Inserts all elements of that set into this set.
    SLLNode prior = null, curr1 = first, curr2 = other.first;
    int comp;
    while (curr2 != null) {
      if (curr1 == null)
        comp = +1;
      else
        comp = (curr1.data).compareTo(curr2.data);
      if (comp < 0) {
      	prior = curr1;
        curr1 = curr1.next;
      } 
      else if (comp > 0) {
        // Insert cur2.element into this set ...
        SLLNode temp = new SLLNode(curr2.data, curr1);
        if (prior == null)
          first = temp;
        else
          prior.next = temp;
        count++;
        prior = temp;
        curr2 = curr2.next;  
      }
      else {   // if (comp == 0)
        prior = curr1;
        curr1 = curr1.next;
        curr2 = curr2.next;
      }
    }
  }

  public void intersection(Set that) {
    LinkedSet other = (LinkedSet) that;
    SLLNode prior = null, curr1 = first, curr2 = other.first;
    int comp;
    while (curr1 != null) {
      if (curr2 == null)
        comp = -1;
      else
        comp = (curr1.data).compareTo(curr2.data);
      if (comp < 0) {
        curr1 = curr1.next;      	
      	if (prior == null)
          first = curr1;
        else
          prior.next = curr1;
        count--;
      }
      else if (comp > 0)
        curr2 = curr2.next;
      else {   // if (comp == 0) 	
        prior = curr1;
        curr1 = curr1.next;
        curr2 = curr2.next;
      }        
    }
  }  
    
  public void difference(Set that) {
    LinkedSet other = (LinkedSet) that;
    SLLNode prior = null, curr1 = first, curr2 = other.first;
    while (curr1 != null && curr2 != null) {
      int comp = (curr1.data).compareTo(curr2.data);
      if (comp < 0) {
      	prior = curr1;
        curr1 = curr1.next;
      }
      else if (comp > 0)
        curr2 = curr2.next;
      else {   // if (comp == 0) 	   
        curr1 = curr1.next;
        if (prior == null)
          first = curr1;
        else
          prior.next = curr1;
        count--;              
        curr2 = curr2.next;
      }        
    }
  }

// Accessors
  public boolean isEmpty() {
    // Return true if and only if this set is empty.
    return count == 0;
  }

  public int size() {
    // Return this set's cardinality.
    return count;
  }

  public boolean contains(Object val) {
    if (val instanceof Comparable)
      return search((Comparable) val) != null;
    else
      return false;
  }

  public boolean equals(Set that) {
    LinkedSet other = (LinkedSet) that;
    if (count != other.count) return false;
    for (SLLNode curr1 = first, curr2 = other.first;
        curr1 != null;
        curr1 = curr1.next, curr2 = curr2.next)
      if (!(curr1.data).equals(curr2.data))
        return false;
    return true;
  }

  public boolean isSubset(Set that) {
  	LinkedSet other = (LinkedSet) that;
    SLLNode curr1 = first, curr2 = other.first;
    while (curr1 != null && curr2 != null) {
      // Compare the current elements of the sets,
      // and make nextElement the lesser of these elements
      // (or the only one if one set is exhausted) ...
      int comp = (curr1.data).compareTo(curr2.data);
      if (comp < 0) return false;
      else if (comp == 0)
        curr1 = curr1.next;
      curr2 = curr2.next;      
    }
    return curr1 == null;
  }

// Auxiliary methods
  private SLLNode search(Comparable val) {
    // Returns the node containing the given element in the given set.
    // Returns null if there is no such node.
    for (SLLNode curr = first;
         curr != null; curr = curr.next) {
      int comp = val.compareTo(curr.data);
      if (comp == 0)
        return curr;
      else if (comp < 0)
        break;
    }
    return null;
  }
    
  public Object clone() {
    LinkedSet that = new LinkedSet();
    SLLNode curr2 = null;
    for (SLLNode curr1 = first; curr1 != null; curr1 = curr1.next) {
      SLLNode temp = new SLLNode(curr1.data, null);
      if (curr2 == null)
        that.first = temp;
      else
        curr2.next = temp;
      curr2 = temp;
    }
	that.count = count;
    return that;
  }
  
  public String toString () {
    String buf = "{ ";
    for (SLLNode curr = first; curr != null; curr = curr.next) {
      if (curr != first) buf += ", ";     
      buf += curr.data.toString();           
    }
    buf += " }";
    return buf;
  }
}
